package com.learn._1exerciseone;

import java.util.ArrayList;
import java.util.List;

public class BigestSubSequence {



    public static void main(String[] args) {

    }


    /**
     * 最笨算法
     * @param input
     * @return
     */

    public static int findBigestSubSequence1(int[] input){

        //将所有子列的所有和计算出来
        int maxSum = 0;
        for(int i = 0;i < input.length;i ++){
            for(int j = i;j < input.length;j ++){
                int thisSum = 0;
                for(int k = i;k <=j;k ++){
                    thisSum += input[k];
                }
                if(thisSum > maxSum){
                    maxSum = thisSum;
                }
            }
        }

        return maxSum;

    }

    /**
     * 也是算出所有子列和，但是利用到了之前的结果
     * @param input
     * @return
     */
    public static int findBigestSubSequence2(int[] input){
        //将所有子列的所有和计算出来
        int maxSum = 0;
        for(int i = 0;i < input.length;i ++){
            int thisSum = 0;
            for(int j = i;j < input.length;j ++){
                thisSum += input[j];
                if(thisSum > maxSum){
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }


    /**
     * 分治法
     * @param input
     * @return
     */
    public static int findBigestSubSequence3(int[] input){
        //将所有子列的所有和计算出来
        findBigestSubSequenceInner(input,0,input.length - 1);
        int maxSum = 0;
        for(int i = 0;i < input.length;i ++){
            int thisSum = 0;
            for(int j = i;j < input.length;j ++){
                thisSum += input[j];
                if(thisSum > maxSum){
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

    private static int findBigestSubSequenceInner(int[] input, int start, int end) {
        if(start == end){
            int tmp;
            return (tmp = input[start]) > 0? tmp: 0;
        }

        int middle = (start + end)/2;
        int first = findBigestSubSequenceInner(input,start,middle);
        int second = findBigestSubSequenceInner(input,middle + 1,end);


        int third = findMiddleBigestSubSequence(input,middle,start,end);


        return first > second? (Math.max(first, third)):(Math.max(second, third));
    }

    private static int findMiddleBigestSubSequence(int[] input, int middle,int start,int end) {

        int left = middle;
        int right = middle + 1;
        int res = 0;
        int tmp = 0;
        int leftTmp = 0;
        while(left >= start || right <= end){
            if(left >= start){
                leftTmp = input[left] + tmp;
            }
            if(leftTmp > res){
                res = leftTmp;
            }

            if(right <= end){
                tmp = input[right ++] + tmp;
            }
            if(tmp > res){
                res = tmp;
            }
            if(left >= start){
                tmp = input[left --] + tmp;
            }
            if(tmp > res){
                res = tmp;
            }
        }
        return res;
    }


    /**
     * 在线计算
     * @param input
     * @return
     */
    public static int findBigestSubSequence4(int[] input){

        //将所有子列的所有和计算出来
        int maxSum = 0;
        int thisSum = 0;
        for(int i = 0;i < input.length;i ++){
            thisSum += input[i];
            if(thisSum > maxSum){
                maxSum = thisSum;
            }else if (thisSum < 0){
                thisSum = 0;
            }
        }

        return maxSum;
    }



}
